/* 
    File: my_allocator.c

    Author: <your name>
            Department of Computer Science
            Texas A&M University
    Date  : <date>

    Modified: 

    This file contains the implementation of the module "MY_ALLOCATOR".

*/

/*--------------------------------------------------------------------------*/
/* DEFINES */
/*--------------------------------------------------------------------------*/

    /* -- (none) -- */

/*--------------------------------------------------------------------------*/
/* INCLUDES */
/*--------------------------------------------------------------------------*/

#include<stdlib.h>
#include "my_allocator.h"

/*--------------------------------------------------------------------------*/
/* DATA STRUCTURES */ 
/*--------------------------------------------------------------------------*/

    void *start;// pointer to the start of the storage
	void **grid;
	int totlength;
					//block=length,char,char,pointer 
	int blocksize,num_lists,headsize;

/*--------------------------------------------------------------------------*/
/* CONSTANTS */
/*--------------------------------------------------------------------------*/

    /* -- (none) -- */

/*--------------------------------------------------------------------------*/
/* FORWARDS */
/*--------------------------------------------------------------------------*/

    /* -- (none) -- */

/*--------------------------------------------------------------------------*/
/* FUNCTIONS FOR MODULE MY_ALLOCATOR */
/*--------------------------------------------------------------------------*/

/* Don't forget to implement "init_allocator" and "release_allocator"! */

unsigned int init_allocator(unsigned int _basic,unsigned int _length)
{
	unsigned int size_head= sizeof(Addr)+sizeof(int)+ 3*(sizeof(char));
	unsigned int basic= _basic+ size_head;
	if(basic<(int)(sizeof(Addr)+sizeof(int)+3*(sizeof(char))))
	{
		printf("Error1:\n");
		return 0;
	}
	if(_length<_basic)
	{
		printf("Error2:\n");
		return 0;
	}
	
	unsigned int y=(_length/_basic);
	y--;
    y |= y >> 1; //
    y |= y >> 2;  // 
    y |= y >> 4;  // i found this method of rounding to the next power of 2 on:
    y |= y >> 8;  //  http://bits.stephan-brumme.com/roundUpToNextPowerOfTwo.html
    y |= y >> 16; // i understand that it basically sets the numbers to a binary formatt of 111111.... and then increments it to get 1000000... the next power of 2
    //y |= y >> 32;//
    y++;
	unsigned int num_blocks=y;
	
	unsigned int total_length= num_blocks*basic; 
	
	start= malloc(total_length*sizeof(char));
	if(start==NULL)
	{
		return 0;
	}
	
	
	num_lists=1;
	while (y >>= 1) 
		{
			num_lists++;
		}
	grid=malloc(num_lists*sizeof(*grid));	
	//sets up the first eleement in grid
	*(int*)start=_length;
	*((int*)start+sizeof(int))='a';
	*((int*)start+sizeof(int)+sizeof(char))='0';
	*((int*)start+sizeof(int)+2*sizeof(char))='b';
	void **temp;
	*(int**)temp=((int*)start+sizeof(int)+3*(sizeof(char)));
	(*(int**)temp)=NULL;
	grid[0]=start;
	// sets up the rest of the ellements in grid
	int i;
	for(i=1;i<num_lists;i++)
	{
	grid[i]=NULL;
	}
	
	totlength=total_length;
	blocksize=basic;
	headsize= size_head;
	return _length;
}

int release_allocator()
{
	free(start);
	free(grid);
	return 0;
}

				
extern Addr my_malloc(unsigned int _length) 
{
	int c,i=0;
	if(_length>totlength)
		return NULL;
	// basically find which minimumm list can accomodate the memory
	while(grid[i]=NULL)
	{
		i++;
	}
	while(grid[i+1]!=NULL&&i<num_lists)
	{
		c=0;
		if(*(int*)grid[i+1]>_length)
		{
			i++;
		}
		else
		{
		c=1;
		break;
		
		}
	}
	char oldbit1=*((int*)grid[i]+sizeof(int));
	char oldbit2=*((int*)grid[i]+sizeof(int)+sizeof(char));
	char oldbit3=*((int*)grid[i]+sizeof(int)+2*sizeof(char));
	
	
//cases:
	//1)the next list has available memory but not enough to allocate the memory ie. c==1; <no splitting>
	//2) the next list has no available memory ie. c==0;
	//	a)if the amount of memory in this list is split then half the current memory is sufficient to allocate the memory; <splitting> and then recursion?
	//	b)if the amount of memory in this list is split then half the current memory is not sufficient to allocate the memory;<no splitting>
		
//1)  
	void **temp;
	void *temp1;
	if(c==1)
	{
	 
		//temp=((int*)grid[i]+headsize-sizeof(Addr));
		temp1= grid[i];
		grid[i]=*((int*)(((int*)grid[i]+headsize)-sizeof(Addr)));
		*((int*)temp1+sizeof(int)+sizeof(char))='1';
		return ((int*)temp1+headsize);
	 
	}

//2a)
	if((*(int*)grid[i])/2>=blocksize&&(*(int*)grid[i])/2>=_length)
	{
		temp=(grid[i]+headsize-sizeof(Addr));
		temp1=(int*)grid[i];
		unsigned int l=*((int*)grid[i]);
		grid[i]=*temp;
		int height=num_lists-i;// calculates height starting at 1;
		int height_child=height-1;
		int nheads=pow(2,height_child-1);// number of heads the child has
		*temp=temp1+(nheads*headsize)+l/2;
		grid[i+1]=temp1;
		*(int*)grid[i+1]=l/2;
		*((int*)grid[i+1]+sizeof(int))='L';//buddy bit
		*((int*)grid[i+1]+sizeof(int)+sizeof(char))='0';
		*((int*)grid[i+1]+sizeof(int)+sizeof(char))=oldbit1;
	// maybe change of bits here
		temp1=*temp;
		*(int*)temp1=l/2;
		*((int*)temp1+sizeof(int))='R';// buddy bit
		*((int*)temp1+sizeof(int)+sizeof(char))='0';
		*((int*)temp1+sizeof(int)+sizeof(char))=oldbit3;
		temp1=((int*)grid[i+1]+headsize-sizeof(Addr));
		*(int**)temp1=NULL;
		
		return my_malloc(_length);// recursion;
	}
	
//2b)
	if((*(int*)grid[i])/2<blocksize||(*(int*)grid[i])/2<_length)
	{
		//temp=((int*)grid[i]+headsize-sizeof(Addr));
		temp1=grid[i];
		grid[i]=((int*)grid[i]+headsize-sizeof(Addr));
		*((int*)temp1+sizeof(int)+sizeof(char))='1';
		return ((int*)temp1+headsize);
	}
	return NULL;
}

extern int my_free(Addr _a) 
{
  if(start<_a&&(start+totlength*sizeof(char))>_a)
  {
	void *temp1;
	//int i= num_lists-1;
	//temp1=_a-sizeof(char)-sizeof(Addr);
	// need to check if the address given is at right spot in the block
		temp1=_a-3*sizeof(char)-sizeof(Addr);
		char buddyval1=*(char*)temp1;
		char buddyval2=*((char*)temp1+sizeof(char));
		char buddyval3=*((char*)temp1+2*sizeof(char));
		temp1=_a-headsize;
		int currlength=*(int*)temp1;
		int y=currlength/(blocksize- headsize);
		int currlist=1;
		while (y >>= 1) 
			{
				currlist++;
			}
		int i= currlist-1;
		void** temp=NULL;
		void*checknext=NULL;
		void *prev=NULL;
		//bool Lbuddy=false;
		//bool Rbuddy=false
//3 cases if the list for that size of memory is unavailable, the list starts after the current location, the list starts before the current location; 
		
		if(buddyval2=='1')
		{
		*((int*)temp1+sizeof(int)+sizeof(char))='1';
			if(buddyval1=='L')
			{
				temp=((int*)temp1+sizeof(int)+3*sizeof(char));
				checknext=*temp;
				if(*((int*)checknext+sizeof(int)+sizeof(char))=='R'&&*((int*)checknext+sizeof(int)+2*sizeof(char))=='0')
				{
					*(int*)temp1=currlength*2;
					
					*temp=(int*)checknext+sizeof(int)+3*sizeof(char);
					*((int*)temp1+sizeof(int))=buddyval3;
					*((int*)temp1+sizeof(int)+sizeof(char))='1';
					if(grid[i-1]=NULL)
					{
						*((int*)temp1+sizeof(int)+2*sizeof(char))=NULL;
						grid[i-1]=temp1;
					}
					else
					{
						*((int*)temp1+sizeof(int)+2*sizeof(char))=grid[i-1];// this logic is probably wrong
						grid[i-1]=temp;
					}
					my_free((int*)temp1);
					return 0;
				}
				else
				{
					*((int*)temp1+sizeof(int)+sizeof(char))='0';
					return 0;
				}
			}
			else
			{
				temp=(grid[i]+sizeof(int)+3*sizeof(char));
				checknext=*temp;
				while(checknext!=temp1)
				{	prev=checknext;
					temp=(checknext+sizeof(int)+2*sizeof(char));
					checknext=*temp;
				}
				if(prev==NULL)
				{
				*((int*)temp1+sizeof(int)+sizeof(char))='0';
				return 0;
				}
				if(*((int*)prev+sizeof(int)+2*sizeof(char))=='0'&&*((int*)prev+sizeof(int)+sizeof(char))=='L')
				{
				checknext=temp1;
				temp=prev;
				
					*(int*)temp1=currlength*2;
					
					*temp=(int*)checknext+sizeof(int)+3*sizeof(char);
					*((int*)temp1+sizeof(int))=buddyval3;
					*((int*)temp1+sizeof(int)+sizeof(char))='1';
					if(grid[i-1]=NULL)
					{
						*((int*)temp1+sizeof(int)+2*sizeof(char))=NULL;
						grid[i-1]=temp1;
					}
					else
					{
						*((int*)temp1+sizeof(int)+2*sizeof(char))=grid[i-1];// this logic is probably wrong
						grid[i-1]=temp;
					}
					my_free((int*)temp1);
					return 0;
				
				}
				else
				{
					*((int*)temp1+sizeof(int)+sizeof(char))='0';
					return 0;
				}
			}
		return 1;
		}
	
	}
	return 1;
}
				
		
